A database is made up of database tables, and database tables of the database can be divided into pages. A buffer pool acts as a cache for a database and can cache pages of database tables. A client can request access to pages of the database, such as by performing a table scan of a database table in the database. If a requested page is cached in the buffer pool, then that page can be accessed by the client without having to physically access the database on secondary storage. However, if a requested page is not cached in the buffer pool, the page must be loaded from secondary storage (i.e. hard disk drives), and placed in the buffer pool. If the buffer pool is full, then pages are evicted to make room in the buffer pool to cache the requested page.
A client can perform a database table scan to access every page of a specific database table. In situations where the amount of pages of the database table exceeds the capacity of the buffer pool, current techniques for evicting pages from the buffer pool may lead to poor page reuse in the buffer pool. For example, given a database table made up of six pages and a buffer pool with a capacity of three pages, the buffer pool may first cache the first page, the second page, and the third page of the six-page database table. Because the buffer pool is now full, an additional page cannot be cached in the buffer pool without first evicting a page from the buffer pool.
A least recently used (LRU) algorithm, which evicts the least recently used page from the buffer pool, is a typical algorithm for determining which pages to evict form the buffer pool. After the first three pages of the database table are cached in the buffer, the LRU algorithm evicts the first page to store the fourth page into the buffer pool, then evicts the second page to store the fifth page into the buffer pool, and finally evicts the third page to cache the sixth page into the buffer pool. After the database table scan finishes, the buffer pool will contain the fourth page, the fifth page, and the sixth page of the database table.
If the client re-scans the same database table, no page reuse occurs because none of the first three pages accessed during the re-scan (i.e., the first page, the second page, and the third page) are cached in the buffer pool, and evicting the fourth page, the fifth page, and the sixth page from the buffer pool to cache the first page, the second page, and the third page into the buffer pool leads to no page reuse in the buffer pool when the fourth page, the fifth page, and the sixth page of the database table is being accessed during the course of the re-scan.